home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / DJLSR106.ARJ / STRING.CC < prev    next >
C/C++ Source or Header  |  1992-03-30  |  29KB  |  1,324 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   String class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation "_String.h"
  24. #endif
  25. #include <_String.h>
  26. #include <std.h>
  27. #include <ctype.h>
  28. #include <values.h>
  29. #include <new.h>
  30. #include <builtin.h>
  31.  
  32. // extern "C" {
  33. #include <regex.h>
  34. // }
  35.  
  36. void String::error(const char* msg) const
  37. {
  38.   (*lib_error_handler)("String", msg);
  39. }
  40.  
  41. String::operator const char*() const
  42. { 
  43.   return (const char*)chars();
  44. }
  45.  
  46. //  globals
  47.  
  48. StrRep  _nilStrRep = { 0, 1, { 0 } }; // nil strings point here
  49. String _nilString;               // nil SubStrings point here
  50.  
  51.  
  52.  
  53.  
  54. /*
  55.  the following inline fcts are specially designed to work
  56.  in support of String classes, and are not meant as generic replacements
  57.  for libc "str" functions.
  58.  
  59.  inline copy fcts -  I like left-to-right from->to arguments.
  60.  all versions assume that `to' argument is non-null
  61.  
  62.  These are worth doing inline, rather than through calls because,
  63.  via procedural integration, adjacent copy calls can be smushed
  64.  together by the optimizer.
  65. */
  66.  
  67. // copy n bytes
  68. inline static void ncopy(const char* from, char* to, int n)
  69. {
  70.   if (from != to) while (--n >= 0) *to++ = *from++;
  71. }
  72.  
  73. // copy n bytes, null-terminate
  74. inline static void ncopy0(const char* from, char* to, int n)
  75. {
  76.   if (from != to) 
  77.   {
  78.     while (--n >= 0) *to++ = *from++;
  79.     *to = 0;
  80.   }
  81.   else
  82.     to[n] = 0;
  83. }
  84.  
  85. // copy until null
  86. inline static void scopy(const char* from, char* to)
  87. {
  88.   if (from != 0) while((*to++ = *from++) != 0);
  89. }
  90.  
  91. // copy right-to-left
  92. inline static void revcopy(const char* from, char* to, short n)
  93. {
  94.   if (from != 0) while (--n >= 0) *to-- = *from--;
  95. }
  96.  
  97.  
  98. inline static int slen(const char* t) // inline  strlen
  99. {
  100.   if (t == 0)
  101.     return 0;
  102.   else
  103.   {
  104.     const char* a = t;
  105.     while (*a++ != 0);
  106.     return a - 1 - t;
  107.   }
  108. }
  109.  
  110. // minimum & maximum representable rep size
  111.  
  112. #define MAXStrRep_SIZE   ((1 << (SHORTBITS - 1)) - 1)
  113. #define MINStrRep_SIZE   16
  114.  
  115. #ifndef MALLOC_MIN_OVERHEAD
  116. #define MALLOC_MIN_OVERHEAD  4
  117. #endif
  118.  
  119. // The basic allocation primitive:
  120. // Always round request to something close to a power of two.
  121. // This ensures a bit of padding, which often means that
  122. // concatenations don't have to realloc. Plus it tends to
  123. // be faster when lots of Strings are created and discarded,
  124. // since just about any version of malloc (op new()) will
  125. // be faster when it can reuse identically-sized chunks
  126.  
  127. inline static StrRep* Snew(int newsiz)
  128. {
  129.   unsigned int siz = sizeof(StrRep) + newsiz + MALLOC_MIN_OVERHEAD;
  130.   unsigned int allocsiz = MINStrRep_SIZE;
  131.   while (allocsiz < siz) allocsiz <<= 1;
  132.   allocsiz -= MALLOC_MIN_OVERHEAD;
  133.   if (allocsiz >= MAXStrRep_SIZE)
  134.     (*lib_error_handler)("String", "Requested length out of range");
  135.     
  136.   StrRep* rep = (StrRep *) new char[allocsiz];
  137.   rep->sz = allocsiz - sizeof(StrRep);
  138.   return rep;
  139. }
  140.  
  141. // Do-something-while-allocating routines.
  142.  
  143. // We live with two ways to signify empty Sreps: either the
  144. // null pointer (0) or a pointer to the nilStrRep.
  145.  
  146. // We always signify unknown source lengths (usually when fed a char*)
  147. // via len == -1, in which case it is computed.
  148.  
  149. // allocate, copying src if nonull
  150.  
  151. StrRep* Salloc(StrRep* old, const char* src, int srclen, int newlen)
  152. {
  153.   if (old == &_nilStrRep) old = 0;
  154.   if (srclen < 0) srclen = slen(src);
  155.   if (newlen < srclen) newlen = srclen;
  156.   StrRep* rep;
  157.   if (old == 0 || newlen > old->sz)
  158.     rep = Snew(newlen);
  159.   else
  160.     rep = old;
  161.  
  162.   rep->len = newlen;
  163.   ncopy0(src, rep->s, srclen);
  164.  
  165.   if (old != rep && old != 0) delete old;
  166.  
  167.   return rep;
  168. }
  169.  
  170. // reallocate: Given the initial allocation scheme, it will
  171. // generally be faster in the long run to get new space & copy
  172. // than to call realloc
  173.  
  174. StrRep* Sresize(StrRep* old, int newlen)
  175. {
  176.   if (old == &_nilStrRep) old = 0;
  177.   StrRep* rep;
  178.   if (old == 0)
  179.     rep = Snew(newlen);
  180.   else if (newlen > old->sz)
  181.   {
  182.     rep = Snew(newlen);
  183.     ncopy0(old->s, rep->s, old->len);
  184.     delete old;
  185.   }
  186.   else
  187.     rep = old;
  188.  
  189.   rep->len = newlen;
  190.  
  191.   return rep;
  192. }
  193.  
  194. // like allocate, but we know that src is a StrRep
  195.  
  196. StrRep* Scopy(StrRep* old, StrRep* s)
  197. {
  198.   if (old == &_nilStrRep) old = 0;
  199.   if (s == &_nilStrRep) s = 0;
  200.   if (old == s) 
  201.     return (old == 0)? &_nilStrRep : old;
  202.   else if (s == 0)
  203.   {
  204.     old->s[0] = 0;
  205.     old->len = 0;
  206.     return old;
  207.   }
  208.   else 
  209.   {
  210.     StrRep* rep;
  211.     int newlen = s->len;
  212.     if (old == 0 || newlen > old->sz)
  213.     {
  214.       if (old != 0) delete old;
  215.       rep = Snew(newlen);
  216.     }
  217.     else
  218.       rep = old;
  219.     rep->len = newlen;
  220.     ncopy0(s->s, rep->s, newlen);
  221.     return rep;
  222.   }
  223. }
  224.  
  225. // allocate & concatenate
  226.  
  227. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen)
  228. {
  229.   if (old == &_nilStrRep) old = 0;
  230.   if (srclen < 0) srclen = slen(s);
  231.   if (tlen < 0) tlen = slen(t);
  232.   int newlen = srclen + tlen;
  233.   StrRep* rep;
  234.  
  235.   if (old == 0 || newlen > old->sz || 
  236.       (t >= old->s && t < &(old->s[old->len]))) // beware of aliasing
  237.     rep = Snew(newlen);
  238.   else
  239.     rep = old;
  240.  
  241.   rep->len = newlen;
  242.  
  243.   ncopy(s, rep->s, srclen);
  244.   ncopy0(t, &(rep->s[srclen]), tlen);
  245.  
  246.   if (old != rep && old != 0) delete old;
  247.  
  248.   return rep;
  249. }
  250.  
  251. // double-concatenate
  252.  
  253. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen,
  254.              const char* u, int ulen)
  255. {
  256.   if (old == &_nilStrRep) old = 0;
  257.   if (srclen < 0) srclen = slen(s);
  258.   if (tlen < 0) tlen = slen(t);
  259.   if (ulen < 0) ulen = slen(u);
  260.   int newlen = srclen + tlen + ulen;
  261.   StrRep* rep;
  262.   if (old == 0 || newlen > old->sz || 
  263.       (t >= old->s && t < &(old->s[old->len])) ||
  264.       (u >= old->s && u < &(old->s[old->len])))
  265.     rep = Snew(newlen);
  266.   else
  267.     rep = old;
  268.  
  269.   rep->len = newlen;
  270.  
  271.   ncopy(s, rep->s, srclen);
  272.   ncopy(t, &(rep->s[srclen]), tlen);
  273.   ncopy0(u, &(rep->s[srclen+tlen]), ulen);
  274.  
  275.   if (old != rep && old != 0) delete old;
  276.  
  277.   return rep;
  278. }
  279.  
  280. // like cat, but we know that new stuff goes in the front of existing rep
  281.  
  282. StrRep* Sprepend(StrRep* old, const char* t, int tlen)
  283. {
  284.   char* s;
  285.   int srclen;
  286.   if (old == &_nilStrRep || old == 0)
  287.   {
  288.     s = 0; old = 0; srclen = 0;
  289.   }
  290.   else
  291.   {
  292.     s = old->s; srclen = old->len;
  293.   }
  294.   if (tlen < 0) tlen = slen(t);
  295.   int newlen = srclen + tlen;
  296.   StrRep* rep;
  297.   if (old == 0 || newlen > old->sz || 
  298.       (t >= old->s && t < &(old->s[old->len])))
  299.     rep = Snew(newlen);
  300.   else
  301.     rep = old;
  302.  
  303.   rep->len = newlen;
  304.  
  305.   revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
  306.   ncopy(t, rep->s, tlen);
  307.  
  308.   if (old != rep && old != 0) delete old;
  309.  
  310.   return rep;
  311. }
  312.  
  313.  
  314. // string compare: first argument is known to be non-null
  315.  
  316. inline static int scmp(const char* a, const char* b)
  317. {
  318.   if (b == 0)
  319.     return *a != 0;
  320.   else
  321.   {
  322.     signed char diff = 0;
  323.     while ((diff = *a - *b++) == 0 && *a++ != 0);
  324.     return diff;
  325.   }
  326. }
  327.  
  328.  
  329. inline static int ncmp(const char* a, int al, const char* b, int bl)
  330. {
  331.   int n = (al <= bl)? al : bl;
  332.   signed char diff;
  333.   while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  334.   return al - bl;
  335. }
  336.  
  337. int fcompare(const String& x, const String& y)
  338. {
  339.   const char* a = x.chars();
  340.   const char* b = y.chars();
  341.   int al = x.length();
  342.   int bl = y.length();
  343.   int n = (al <= bl)? al : bl;
  344.   signed char diff = 0;
  345.   while (n-- > 0)
  346.   {
  347.     char ac = *a++;
  348.     char bc = *b++;
  349.     if ((diff = ac - bc) != 0)
  350.     {
  351.       if (ac >= 'a' && ac <= 'z')
  352.         ac = ac - 'a' + 'A';
  353.       if (bc >= 'a' && bc <= 'z')
  354.         bc = bc - 'a' + 'A';
  355.       if ((diff = ac - bc) != 0)
  356.         return diff;
  357.     }
  358.   }
  359.   return al - bl;
  360. }
  361.  
  362. // these are not inline, but pull in the above inlines, so are 
  363. // pretty fast
  364.  
  365. int compare(const String& x, const char* b)
  366. {
  367.   return scmp(x.chars(), b);
  368. }
  369.  
  370. int compare(const String& x, const String& y)
  371. {
  372.   return scmp(x.chars(), y.chars());
  373. }
  374.  
  375. int compare(const String& x, const SubString& y)
  376. {
  377.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  378. }
  379.  
  380. int compare(const SubString& x, const String& y)
  381. {
  382.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  383. }
  384.  
  385. int compare(const SubString& x, const SubString& y)
  386. {
  387.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  388. }
  389.  
  390. int compare(const SubString& x, const char* b)
  391. {
  392.   if (b == 0)
  393.     return x.length();
  394.   else
  395.   {
  396.     const char* a = x.chars();
  397.     int n = x.length();
  398.     signed char diff;
  399.     while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  400.     return (*b == 0) ? 0 : -1;
  401.   }
  402. }
  403.  
  404. /*
  405.  index fcts
  406. */
  407.  
  408. int String::search(int start, int sl, char c) const
  409. {
  410.   const char* s = chars();
  411.   if (sl > 0)
  412.   {
  413.     if (start >= 0)
  414.     {
  415.       const char* a = &(s[start]);
  416.       const char* lasta = &(s[sl]);
  417.       while (a < lasta) if (*a++ == c) return --a - s;
  418.     }
  419.     else
  420.     {
  421.       const char* a = &(s[sl + start + 1]);
  422.       while (--a >= s) if (*a == c) return a - s;
  423.     }
  424.   }
  425.   return -1;
  426. }
  427.  
  428. int String::search(int start, int sl, const char* t, int tl) const
  429. {
  430.   const char* s = chars();
  431.   if (tl < 0) tl = slen(t);
  432.   if (sl > 0 && tl > 0)
  433.   {
  434.     if (start >= 0)
  435.     {
  436.       const char* lasts = &(s[sl - tl]);
  437.       const char* lastt = &(t[tl]);
  438.       const char* p = &(s[start]);
  439.  
  440.       while (p <= lasts)
  441.       {
  442.         const char* x = p++;
  443.         const char* y = t;
  444.         while (*x++ == *y++) if (y >= lastt) return --p - s;
  445.       }
  446.     }
  447.     else
  448.     {
  449.       const char* firsts = &(s[tl - 1]);
  450.       const char* lastt =  &(t[tl - 1]);
  451.       const char* p = &(s[sl + start + 1]); 
  452.  
  453.       while (--p >= firsts)
  454.       {
  455.         const char* x = p;
  456.         const char* y = lastt;
  457.         while (*x-- == *y--) if (y < t) return ++x - s;
  458.       }
  459.     }
  460.   }
  461.   return -1;
  462. }
  463.  
  464. int String::match(int start, int sl, int exact, const char* t, int tl) const
  465. {
  466.   if (tl < 0) tl = slen(t);
  467.  
  468.   if (start < 0)
  469.   {
  470.     start = sl + start - tl + 1;
  471.     if (start < 0 || (exact && start != 0))
  472.       return -1;
  473.   }
  474.   else if (exact && sl - start != tl)
  475.     return -1;
  476.  
  477.   if (sl == 0 || tl == 0 || sl - start < tl || start >= sl)
  478.     return -1;
  479.  
  480.   int n = tl;
  481.   const char* s = &(rep->s[start]);
  482.   while (--n >= 0) if (*s++ != *t++) return -1;
  483.   return tl;
  484. }
  485.  
  486. void SubString::assign(StrRep* ysrc, const char* ys, int ylen)
  487. {
  488.   if (&S == &_nilString) return;
  489.  
  490.   if (ylen < 0) ylen = slen(ys);
  491.   StrRep* targ = S.rep;
  492.   int sl = targ->len - len + ylen;
  493.  
  494.   if (ysrc == targ || sl >= targ->sz)
  495.   {
  496.     StrRep* oldtarg = targ;
  497.     targ = Sresize(0, sl);
  498.     ncopy(oldtarg->s, targ->s, pos);
  499.     ncopy(ys, &(targ->s[pos]), ylen);
  500.     scopy(&(oldtarg->s[pos + len]), &(targ->s[pos + ylen]));
  501.     delete oldtarg;
  502.   }
  503.   else if (len == ylen)
  504.     ncopy(ys, &(targ->s[pos]), len);
  505.   else if (ylen < len)
  506.   {
  507.     ncopy(ys, &(targ->s[pos]), ylen);
  508.     scopy(&(targ->s[pos + len]), &(targ->s[pos + ylen]));
  509.   }
  510.   else
  511.   {
  512.     revcopy(&(targ->s[targ->len]), &(targ->s[sl]), targ->len-pos-len +1);
  513.     ncopy(ys, &(targ->s[pos]), ylen);
  514.   }
  515.   targ->len = sl;
  516.   S.rep = targ;
  517. }
  518.  
  519.  
  520.  
  521. /*
  522.  * substitution
  523.  */
  524.  
  525.  
  526. int String::_gsub(const char* pat, int pl, const char* r, int rl)
  527. {
  528.   int nmatches = 0;
  529.   if (pl < 0) pl = slen(pat);
  530.   if (rl < 0) rl = slen(r);
  531.   int sl = length();
  532.   if (sl <= 0 || pl <= 0 || sl < pl)
  533.     return nmatches;
  534.   
  535.   const char* s = chars();
  536.  
  537.   // prepare to make new rep
  538.   StrRep* nrep = 0;
  539.   int nsz = 0;
  540.   char* x = 0;
  541.  
  542.   int si = 0;
  543.   int xi = 0;
  544.   int remaining = sl;
  545.  
  546.   while (remaining >= pl)
  547.   {
  548.     int pos = search(si, sl, pat, pl);
  549.     if (pos < 0)
  550.       break;
  551.     else
  552.     {
  553.       ++nmatches;
  554.       int mustfit = xi + remaining + rl - pl;
  555.       if (mustfit >= nsz)
  556.       {
  557.         if (nrep != 0) nrep->len = xi;
  558.         nrep = Sresize(nrep, mustfit);
  559.         nsz = nrep->sz;
  560.         x = nrep->s;
  561.       }
  562.       pos -= si;
  563.       ncopy(&(s[si]), &(x[xi]), pos);
  564.       ncopy(r, &(x[xi + pos]), rl);
  565.       si += pos + pl;
  566.       remaining -= pos + pl;
  567.       xi += pos + rl;
  568.     }
  569.   }
  570.  
  571.   if (nrep == 0)
  572.   {
  573.     if (nmatches == 0)
  574.       return nmatches;
  575.     else
  576.       nrep = Sresize(nrep, xi+remaining);
  577.   }
  578.  
  579.   ncopy0(&(s[si]), &(x[xi]), remaining);
  580.   nrep->len = xi + remaining;
  581.  
  582.   if (nrep->len <= rep->sz)   // fit back in if possible
  583.   {
  584.     rep->len = nrep->len;
  585.     ncopy0(nrep->s, rep->s, rep->len);
  586.     delete(nrep);
  587.   }
  588.   else
  589.   {
  590.     delete(rep);
  591.     rep = nrep;
  592.   }
  593.   return nmatches;
  594. }
  595.  
  596. int String::_gsub(const Regex& pat, const char* r, int rl)
  597. {
  598.   int nmatches = 0;
  599.   int sl = length();
  600.   if (sl <= 0)
  601.     return nmatches;
  602.  
  603.   if (rl < 0) rl = slen(r);
  604.  
  605.   const char* s = chars();
  606.  
  607.   StrRep* nrep = 0;
  608.   int nsz = 0;
  609.  
  610.   char* x = 0;
  611.  
  612.   int si = 0;
  613.   int xi = 0;
  614.   int remaining = sl;
  615.   int  pos, pl = 0;                  // how long is a regular expression?
  616.  
  617.   while (remaining > 0)
  618.   {
  619.     pos = pat.search(s, sl, pl, si); // unlike string search, the pos returned here is absolute
  620.     if (pos < 0 || pl <= 0)
  621.       break;
  622.     else
  623.     {
  624.       ++nmatches;
  625.       int mustfit = xi + remaining + rl - pl;
  626.       if (mustfit >= nsz)
  627.       {
  628.         if (nrep != 0) nrep->len = xi;
  629.         nrep = Sresize(nrep, mustfit);
  630.         x = nrep->s;
  631.         nsz = nrep->sz;
  632.       }
  633.       pos -= si;
  634.       ncopy(&(s[si]), &(x[xi]), pos);
  635.       ncopy(r, &(x[xi + pos]), rl);
  636.       si += pos + pl;
  637.       remaining -= pos + pl;
  638.       xi += pos + rl;
  639.     }
  640.   }
  641.  
  642.   if (nrep == 0)
  643.   {
  644.     if (nmatches == 0)
  645.       return nmatches;
  646.     else
  647.       nrep = Sresize(nrep, xi+remaining);
  648.   }
  649.  
  650.   ncopy0(&(s[si]), &(x[xi]), remaining);
  651.   nrep->len = xi + remaining;
  652.  
  653.   if (nrep->len <= rep->sz)   // fit back in if possible
  654.   {
  655.     rep->len = nrep->len;
  656.     ncopy0(nrep->s, rep->s, rep->len);
  657.     delete(nrep);
  658.   }
  659.   else
  660.   {
  661.     delete(rep);
  662.     rep = nrep;
  663.   }
  664.   return nmatches;
  665. }
  666.  
  667.  
  668. /*
  669.  * deletion
  670.  */
  671.  
  672. void String::del(int pos, int len)
  673. {
  674.   if (pos < 0 || len <= 0 || (unsigned)(pos + len) > length()) return;
  675.   int nlen = length() - len;
  676.   int first = pos + len;
  677.   ncopy0(&(rep->s[first]), &(rep->s[pos]), length() - first);
  678.   rep->len = nlen;
  679. }
  680.  
  681. void String::del(const Regex& r, int startpos)
  682. {
  683.   int mlen;
  684.   int first = r.search(chars(), length(), mlen, startpos);
  685.   del(first, mlen);
  686. }
  687.  
  688. void String::del(const char* t, int startpos)
  689. {
  690.   int tlen = slen(t);
  691.   int p = search(startpos, length(), t, tlen);
  692.   del(p, tlen);
  693. }
  694.  
  695. void String::del(const String& y, int startpos)
  696. {
  697.   del(search(startpos, length(), y.chars(), y.length()), y.length());
  698. }
  699.  
  700. void String::del(const SubString& y, int startpos)
  701. {
  702.   del(search(startpos, length(), y.chars(), y.length()), y.length());
  703. }
  704.  
  705. void String::del(char c, int startpos)
  706. {
  707.   del(search(startpos, length(), c), 1);
  708. }
  709.  
  710. /*
  711.  * substring extraction
  712.  */
  713.  
  714.  
  715. SubString String::at(int first, int len)
  716. {
  717.   return _substr(first, len);
  718. }
  719.  
  720. SubString String::operator() (int first, int len)
  721. {
  722.   return _substr(first, len);
  723. }
  724.  
  725. SubString String::before(int pos)
  726. {
  727.   return _substr(0, pos);
  728. }
  729.  
  730. SubString String::through(int pos)
  731. {
  732.   return _substr(0, pos+1);
  733. }
  734.  
  735. SubString String::after(int pos)
  736. {
  737.   return _substr(pos + 1, length() - (pos + 1));
  738. }
  739.  
  740. SubString String::from(int pos)
  741. {
  742.   return _substr(pos, length() - pos);
  743. }
  744.  
  745. SubString String::at(const String& y, int startpos)
  746. {
  747.   int first = search(startpos, length(), y.chars(), y.length());
  748.   return _substr(first,  y.length());
  749. }
  750.  
  751. SubString String::at(const SubString& y, int startpos)
  752. {
  753.   int first = search(startpos, length(), y.chars(), y.length());
  754.   return _substr(first, y.length());
  755. }
  756.  
  757. SubString String::at(const Regex& r, int startpos)
  758. {
  759.   int mlen;
  760.   int first = r.search(chars(), length(), mlen, startpos);
  761.   return _substr(first, mlen);
  762. }
  763.  
  764. SubString String::at(const char* t, int startpos)
  765. {
  766.   int tlen = slen(t);
  767.   int first = search(startpos, length(), t, tlen);
  768.   return _substr(first, tlen);
  769. }
  770.  
  771. SubString String::at(char c, int startpos)
  772. {
  773.   int first = search(startpos, length(), c);
  774.   return _substr(first, 1);
  775. }
  776.  
  777. SubString String::before(const String& y, int startpos)
  778. {
  779.   int last = search(startpos, length(), y.chars(), y.length());
  780.   return _substr(0, last);
  781. }
  782.  
  783. SubString String::before(const SubString& y, int startpos)
  784. {
  785.   int last = search(startpos, length(), y.chars(), y.length());
  786.   return _substr(0, last);
  787. }
  788.  
  789. SubString String::before(const Regex& r, int startpos)
  790. {
  791.   int mlen;
  792.   int first = r.search(chars(), length(), mlen, startpos);
  793.   return _substr(0, first);
  794. }
  795.  
  796. SubString String::before(char c, int startpos)
  797. {
  798.   int last = search(startpos, length(), c);
  799.   return _substr(0, last);
  800. }
  801.  
  802. SubString String::before(const char* t, int startpos)
  803. {
  804.   int tlen = slen(t);
  805.   int last = search(startpos, length(), t, tlen);
  806.   return _substr(0, last);
  807. }
  808.  
  809. SubString String::through(const String& y, int startpos)
  810. {
  811.   int last = search(startpos, length(), y.chars(), y.length());
  812.   if (last >= 0) last += y.length();
  813.   return _substr(0, last);
  814. }
  815.  
  816. SubString String::through(const SubString& y, int startpos)
  817. {
  818.   int last = search(startpos, length(), y.chars(), y.length());
  819.   if (last >= 0) last += y.length();
  820.   return _substr(0, last);
  821. }
  822.  
  823. SubString String::through(const Regex& r, int startpos)
  824. {
  825.   int mlen;
  826.   int first = r.search(chars(), length(), mlen, startpos);
  827.   if (first >= 0) first += mlen;
  828.   return _substr(0, first);
  829. }
  830.  
  831. SubString String::through(char c, int startpos)
  832. {
  833.   int last = search(startpos, length(), c);
  834.   if (last >= 0) last += 1;
  835.   return _substr(0, last);
  836. }
  837.  
  838. SubString String::through(const char* t, int startpos)
  839. {
  840.   int tlen = slen(t);
  841.   int last = search(startpos, length(), t, tlen);
  842.   if (last >= 0) last += tlen;
  843.   return _substr(0, last);
  844. }
  845.  
  846. SubString String::after(const String& y, int startpos)
  847. {
  848.   int first = search(startpos, length(), y.chars(), y.length());
  849.   if (first >= 0) first += y.length();
  850.   return _substr(first, length() - first);
  851. }
  852.  
  853. SubString String::after(const SubString& y, int startpos)
  854. {
  855.   int first = search(startpos, length(), y.chars(), y.length());
  856.   if (first >= 0) first += y.length();
  857.   return _substr(first, length() - first);
  858. }
  859.  
  860. SubString String::after(char c, int startpos)
  861. {
  862.   int first = search(startpos, length(), c);
  863.   if (first >= 0) first += 1;
  864.   return _substr(first, length() - first);
  865. }
  866.  
  867. SubString String::after(const Regex& r, int startpos)
  868. {
  869.   int mlen;
  870.   int first = r.search(chars(), length(), mlen, startpos);
  871.   if (first >= 0) first += mlen;
  872.   return _substr(first, length() - first);
  873. }
  874.  
  875. SubString String::after(const char* t, int startpos)
  876. {
  877.   int tlen = slen(t);
  878.   int first = search(startpos, length(), t, tlen);
  879.   if (first >= 0) first += tlen;
  880.   return _substr(first, length() - first);
  881. }
  882.  
  883. SubString String::from(const String& y, int startpos)
  884. {
  885.   int first = search(startpos, length(), y.chars(), y.length());
  886.   return _substr(first, length() - first);
  887. }
  888.  
  889. SubString String::from(const SubString& y, int startpos)
  890. {
  891.   int first = search(startpos, length(), y.chars(), y.length());
  892.   return _substr(first, length() - first);
  893. }
  894.  
  895. SubString String::from(const Regex& r, int startpos)
  896. {
  897.   int mlen;
  898.   int first = r.search(chars(), length(), mlen, startpos);
  899.   return _substr(first, length() - first);
  900. }
  901.  
  902. SubString String::from(char c, int startpos)
  903. {
  904.   int first = search(startpos, length(), c);
  905.   return _substr(first, length() - first);
  906. }
  907.  
  908. SubString String::from(const char* t, int startpos)
  909. {
  910.   int tlen = slen(t);
  911.   int first = search(startpos, length(), t, tlen);
  912.   return _substr(first, length() - first);
  913. }
  914.  
  915.  
  916.  
  917. /*
  918.  * split/join
  919.  */
  920.  
  921.  
  922. int split(const String& src, String results[], int n, const String& sep)
  923. {
  924.   String x = src;
  925.   const char* s = x.chars();
  926.   int sl = x.length();
  927.   int i = 0;
  928.   int pos = 0;
  929.   while (i < n && pos < sl)
  930.   {
  931.     int p = x.search(pos, sl, sep.chars(), sep.length());
  932.     if (p < 0)
  933.       p = sl;
  934.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  935.     i++;
  936.     pos = p + sep.length();
  937.   }
  938.   return i;
  939. }
  940.  
  941. int split(const String& src, String results[], int n, const Regex& r)
  942. {
  943.   String x = src;
  944.   const char* s = x.chars();
  945.   int sl = x.length();
  946.   int i = 0;
  947.   int pos = 0;
  948.   int p, matchlen;
  949.   while (i < n && pos < sl)
  950.   {
  951.     p = r.search(s, sl, matchlen, pos);
  952.     if (p < 0)
  953.       p = sl;
  954.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  955.     i++;
  956.     pos = p + matchlen;
  957.   }
  958.   return i;
  959. }
  960.  
  961.  
  962. #if defined(__GNUG__) && !defined(NO_NRV)
  963.  
  964. String join(String src[], int n, const String& separator) return x;
  965. {
  966.   String sep = separator;
  967.   int xlen = 0;
  968.   for (int i = 0; i < n; ++i)
  969.     xlen += src[i].length();
  970.   xlen += (n - 1) * sep.length();
  971.  
  972.   x.alloc(xlen);
  973.  
  974.   int j = 0;
  975.   
  976.   for (i = 0; i < n - 1; ++i)
  977.   {
  978.     ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
  979.     j += src[i].length();
  980.     ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
  981.     j += sep.length();
  982.   }
  983.   ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
  984. }
  985.  
  986. #else
  987.  
  988. String join(String src[], int n, const String& separator)
  989. {
  990.   String x;
  991.   String sep = separator;
  992.   int xlen = 0;
  993.   for (int i = 0; i < n; ++i)
  994.     xlen += src[i].length();
  995.   xlen += (n - 1) * sep.length();
  996.  
  997.   x.alloc(xlen);
  998.  
  999.   int j = 0;
  1000.   
  1001.   for (i = 0; i < n - 1; ++i)
  1002.   {
  1003.     ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
  1004.     j += src[i].length();
  1005.     ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
  1006.     j += sep.length();
  1007.   }
  1008.   ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
  1009.   return x;
  1010. }
  1011.  
  1012. #endif
  1013.   
  1014. /*
  1015.  misc
  1016. */
  1017.  
  1018.     
  1019. StrRep* Sreverse(StrRep* src, StrRep* dest)
  1020. {
  1021.   int n = src->len;
  1022.   if (src != dest)
  1023.     dest = Salloc(dest, src->s, n, n);
  1024.   if (n > 0)
  1025.   {
  1026.     char* a = dest->s;
  1027.     char* b = &(a[n - 1]);
  1028.     while (a < b)
  1029.     {
  1030.       char t = *a;
  1031.       *a++ = *b;
  1032.       *b-- = t;
  1033.     }
  1034.   }
  1035.   return dest;
  1036. }
  1037.  
  1038.  
  1039. StrRep* Supcase(StrRep* src, StrRep* dest)
  1040. {
  1041.   int n = src->len;
  1042.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1043.   char* p = dest->s;
  1044.   char* e = &(p[n]);
  1045.   for (; p < e; ++p) if (islower(*p)) *p = toupper(*p);
  1046.   return dest;
  1047. }
  1048.  
  1049. StrRep* Sdowncase(StrRep* src, StrRep* dest)
  1050. {
  1051.   int n = src->len;
  1052.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1053.   char* p = dest->s;
  1054.   char* e = &(p[n]);
  1055.   for (; p < e; ++p) if (isupper(*p)) *p = tolower(*p);
  1056.   return dest;
  1057. }
  1058.  
  1059. StrRep* Scapitalize(StrRep* src, StrRep* dest)
  1060. {
  1061.   int n = src->len;
  1062.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1063.  
  1064.   char* p = dest->s;
  1065.   char* e = &(p[n]);
  1066.   for (; p < e; ++p)
  1067.   {
  1068.     int at_word;
  1069.     if (at_word = islower(*p))
  1070.       *p = toupper(*p);
  1071.     else 
  1072.       at_word = isupper(*p) || isdigit(*p);
  1073.  
  1074.     if (at_word)
  1075.     {
  1076.       while (++p < e)
  1077.       {
  1078.         if (isupper(*p))
  1079.           *p = tolower(*p);
  1080.         else if (!islower(*p) && !isdigit(*p))
  1081.           break;
  1082.       }
  1083.     }
  1084.   }
  1085.   return dest;
  1086. }
  1087.  
  1088. #if defined(__GNUG__) && !defined(NO_NRV)
  1089.  
  1090. String replicate(char c, int n) return w;
  1091. {
  1092.   w.rep = Sresize(w.rep, n);
  1093.   char* p = w.rep->s;
  1094.   while (n-- > 0) *p++ = c;
  1095.   *p = 0;
  1096. }
  1097.  
  1098. String replicate(const String& y, int n) return w
  1099. {
  1100.   int len = y.length();
  1101.   w.rep = Sresize(w.rep, n * len);
  1102.   char* p = w.rep->s;
  1103.   while (n-- > 0)
  1104.   {
  1105.     ncopy(y.chars(), p, len);
  1106.     p += len;
  1107.   }
  1108.   *p = 0;
  1109. }
  1110.  
  1111. String common_prefix(const String& x, const String& y, int startpos) return r;
  1112. {
  1113.   const char* xchars = x.chars();
  1114.   const char* ychars = y.chars();
  1115.   const char* xs = &(xchars[startpos]);
  1116.   const char* ss = xs;
  1117.   const char* topx = &(xchars[x.length()]);
  1118.   const char* ys = &(ychars[startpos]);
  1119.   const char* topy = &(ychars[y.length()]);
  1120.   for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1121.   r.rep = Salloc(r.rep, ss, l, l);
  1122. }
  1123.  
  1124. String common_suffix(const String& x, const String& y, int startpos) return r;
  1125. {
  1126.   const char* xchars = x.chars();
  1127.   const char* ychars = y.chars();
  1128.   const char* xs = &(xchars[x.length() + startpos]);
  1129.   const char* botx = xchars;
  1130.   const char* ys = &(ychars[y.length() + startpos]);
  1131.   const char* boty = ychars;
  1132.   for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1133.   r.rep = Salloc(r.rep, ++xs, l, l);
  1134. }
  1135.  
  1136. #else
  1137.  
  1138. String replicate(char c, int n)
  1139. {
  1140.   String w;
  1141.   w.rep = Sresize(w.rep, n);
  1142.   char* p = w.rep->s;
  1143.   while (n-- > 0) *p++ = c;
  1144.   *p = 0;
  1145.   return w;
  1146. }
  1147.  
  1148. String replicate(const String& y, int n)
  1149. {
  1150.   String w;
  1151.   int len = y.length();
  1152.   w.rep = Sresize(w.rep, n * len);
  1153.   char* p = w.rep->s;
  1154.   while (n-- > 0)
  1155.   {
  1156.     ncopy(y.chars(), p, len);
  1157.     p += len;
  1158.   }
  1159.   *p = 0;
  1160.   return w;
  1161. }
  1162.  
  1163. String common_prefix(const String& x, const String& y, int startpos)
  1164. {
  1165.   String r;
  1166.   const char* xchars = x.chars();
  1167.   const char* ychars = y.chars();
  1168.   const char* xs = &(xchars[startpos]);
  1169.   const char* ss = xs;
  1170.   const char* topx = &(xchars[x.length()]);
  1171.   const char* ys = &(ychars[startpos]);
  1172.   const char* topy = &(ychars[y.length()]);
  1173.   for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1174.   r.rep = Salloc(r.rep, ss, l, l);
  1175.   return r;
  1176. }
  1177.  
  1178. String common_suffix(const String& x, const String& y, int startpos) 
  1179. {
  1180.   String r;
  1181.   const char* xchars = x.chars();
  1182.   const char* ychars = y.chars();
  1183.   const char* xs = &(xchars[x.length() + startpos]);
  1184.   const char* botx = xchars;
  1185.   const char* ys = &(ychars[y.length() + startpos]);
  1186.   const char* boty = ychars;
  1187.   for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1188.   r.rep = Salloc(r.rep, ++xs, l, l);
  1189.   return r;
  1190. }
  1191.  
  1192. #endif
  1193.  
  1194. // IO
  1195.  
  1196. istream& operator>>(istream& s, String& x)
  1197. {
  1198. #ifdef _OLD_STREAMS
  1199.   if (!s.good())
  1200.   {
  1201.     return s;
  1202.   }
  1203.   s >> ws;
  1204.   if (!s.good())
  1205.   {
  1206.     return s;
  1207.   }
  1208. #else
  1209.   if (!s.ipfx(0))
  1210.   {
  1211.     s.set(ios::failbit); // Redundant if using GNU iostreams.
  1212.     return s;
  1213.   }
  1214. #endif
  1215.   char ch;
  1216.   int i = 0;
  1217.   x.rep = Sresize(x.rep, 20);
  1218.   while (s.get(ch))
  1219.   {
  1220.     if (isspace(ch))
  1221.       break;
  1222.     if (i >= x.rep->sz - 1)
  1223.       x.rep = Sresize(x.rep, i+1);
  1224.     x.rep->s[i++] = ch;
  1225.   }
  1226.   x.rep->s[i] = 0;
  1227.   x.rep->len = i;
  1228.   if(i == 0) s.clear(_bad);
  1229.   return s;
  1230. }
  1231.  
  1232. int readline(istream& s, String& x, char terminator, int discard)
  1233. {
  1234. #ifdef _OLD_STREAMS
  1235.   if (!s.good())
  1236. #else
  1237.   if (!s.ipfx(0))
  1238. #endif
  1239.   {
  1240.     return 0;
  1241.   }
  1242.   char ch;
  1243.   int i = 0;
  1244.   x.rep = Sresize(x.rep, 80);
  1245.   while (s.get(ch))
  1246.   {
  1247.     if (ch != terminator || !discard)
  1248.     {
  1249.       if (i >= x.rep->sz - 1)
  1250.         x.rep = Sresize(x.rep, i+1);
  1251.       x.rep->s[i++] = ch;
  1252.     }
  1253.     if (ch == terminator)
  1254.       break;
  1255.   }
  1256.   x.rep->s[i] = 0;
  1257.   x.rep->len = i;
  1258.   return i;
  1259. }
  1260.  
  1261.  
  1262. ostream& operator<<(ostream& s, const SubString& x)
  1263. { 
  1264.   const char* a = x.chars();
  1265.   const char* lasta = &(a[x.length()]);
  1266.   while (a < lasta)
  1267.     s.put(*a++);
  1268.   return(s);
  1269. }
  1270.  
  1271. // from John.Willis@FAS.RI.CMU.EDU
  1272.  
  1273. int String::freq(const SubString& y) const
  1274. {
  1275.   int found = 0;
  1276.   for (unsigned int i = 0; i < length(); i++) 
  1277.     if (match(i,length(),0,y.chars(), y.length())>= 0) found++;
  1278.   return(found);
  1279. }
  1280.  
  1281. int String::freq(const String& y) const
  1282. {
  1283.   int found = 0;
  1284.   for (unsigned int i = 0; i < length(); i++) 
  1285.     if (match(i,length(),0,y.chars(),y.length()) >= 0) found++;
  1286.   return(found);
  1287. }
  1288.  
  1289. int String::freq(const char* t) const
  1290. {
  1291.   int found = 0;
  1292.   for (unsigned int i = 0; i < length(); i++) 
  1293.     if (match(i,length(),0,t) >= 0) found++;
  1294.   return(found);
  1295. }
  1296.  
  1297. int String::freq(char c) const
  1298. {
  1299.   int found = 0;
  1300.   for (unsigned int i = 0; i < length(); i++) 
  1301.     if (match(i,length(),0,&c,1) >= 0) found++;
  1302.   return(found);
  1303. }
  1304.  
  1305.  
  1306. int String::OK() const
  1307. {
  1308.   int v = rep != 0;             // have a rep
  1309.   v &= rep->len <= rep->sz;     // string within bounds
  1310.   v &= rep->s[rep->len] == 0;   // null-terminated
  1311.   if (!v) error("invariant failure");
  1312.   return v;
  1313. }
  1314.  
  1315. int SubString::OK() const
  1316. {
  1317.   int v = S != 0;               // have a String;
  1318.   v &= S.OK();                 // that is legal
  1319.   v &= pos + len >= S.rep->len;// pos and len within bounds
  1320.   if (!v) S.error("SubString invariant failure");
  1321.   return v;
  1322. }
  1323.  
  1324.